package com.lihepeng.leecode.frequency.LinkedList;

/**
 * 单向链表的排序
 * 使用归并排序
 */
public class Solution12 {
    /**
     * 解决方案
     * 使用合并排序的方案
     * 针对链表做拆分  拆分方案是快慢指针的方案
     * 然后对拆分之后的链表做合并
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        if (head ==null || head.next ==null) {
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null && fast.next !=null) {
            fast = fast.next;
            fast = fast.next;
            slow = slow.next;
        }
        ListNode temp = slow.next ;
        // 截断
        slow.next = null;

        ListNode left = sortInList(head);
        ListNode right =sortInList(temp);
        ListNode dumpNode = new ListNode(-1);
        ListNode h = dumpNode;
        // 合并双向链表
        while (left!=null && right !=null) {
            if (left.val<right.val) {
                h.next = left;
                left = left.next;
            }else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left!=null?left:right;
        return h.next;
    }
}
